﻿#define _CRT_SECURE_NO_WARNINGS

//int* printNumbers(int n, int* returnSize) 
//{
//	*returnSize = pow(10, n) - 1; //确定最大的数字
//	int* arr = (int*)malloc(sizeof(int) * (*returnSize));//申请足够大小的空间
//	for (int i = 0; i < *returnSize; i++) 
//	{
//		arr[i] = i + 1;//下标从0开始，而数值从1开始
//	}
//	return arr;
//}
//#include <stdio.h>
//int main()
//{
//	int m;
//	while (~scanf("%d", &m)) {
//		int start = m * (m - 1) + 1;//找到对应m^3的起始奇数
//		char buf[10240] = { 0 };
//		//sprintf(buf, format, ...) 与printf用法类似，格式化字符串但是不用于打印而是放到一个buf中
//		sprintf(buf, "%d", start);//先将起始奇数转换成为字符串存入buf中
//		for (int i = 1; i < m; i++) {
//			//然后将紧随随后的m-1个奇数数字转换为字符串，按照指定格式放入buf中
//			//%s+%d, 要求先有一个字符串，然后是+符号，然后是个数字的格式，对应是buf原先的数据，和奇数
//			sprintf(buf, "%s+%d", buf, start += 2);
//		}
//		printf("%s\n", buf);
//	}
//	return 0;
//}
//#include <stdio.h>
//int i;
//void prt()
//{
//	for (i = 5; i < 8; i++)
//		printf("%c", '*');
//	printf("\t");
//}
//int main()
//{
//	for (i = 5; i <= 8; i++)
//		prt();
//	return 0;
//}

//int minNumberInRotateArray(int* rotateArray, int rotateArrayLen) {
//	if (rotateArrayLen == 0) return 0;
//	int left = 0, right = rotateArrayLen - 1, mid;
//	if (rotateArray[right] > rotateArray[left]) return rotateArray[0];
//	while (left < right) {
//		mid = left + (right - left) / 2;
//		if (rotateArray[mid] > rotateArray[right]) left = mid + 1;
//		else if (rotateArray[mid] == rotateArray[right]) right--;
//		else right = mid;
//	}
//	return rotateArray[left];
//}

//集合 s 包含从 1 到 n 的整数。不幸的是，因为数据错误，导致集合里面某一个数字复制了成了集合里面的另外一个数字的值，导致集合 丢失了一个数字 并且 有一个数字重复 。
//
//给定一个数组 nums 代表了集合 S 发生错误后的结果。
//
//请你找出重复出现的整数，再找到丢失的整数，将它们以数组的形式返回。

//int* findErrorNums(int* nums, int numsSize, int* returnSize) {
//    *returnSize = 2;
//    int* arr = (int*)calloc(numsSize + 1, sizeof(int));
//    int* ret = (int*)calloc(*returnSize, sizeof(int));
//    int cur_sum = 0;
//    int old_sum = 0;
//    for (int i = 0; i < numsSize; i++)
//    {
//        if (arr[nums[i]] == 1)
//        {
//            ret[0] = nums[i];
//        }
//        arr[nums[i]] = 1;
//        old_sum += i + 1;
//        cur_sum += nums[i];
//    }
//    ret[1] = old_sum - (cur_sum - ret[0]);
//
//    return ret;
//}
//
//
//int* findErrorNums(int* nums, int numsSize, int* returnSize) {
//    *returnSize = 2;
//    //遍历nums数组，将其中数据对应的位置1， 哪一位如果已经重置过则意味着数据重复了
//    int* arr = (int*)calloc(numsSize + 1, sizeof(int));//申请numsSize个整形空间，并初始化为0
//    int* ret = (int*)calloc(*returnSize, sizeof(int));//申请2个整形空间，并初始化为0
//    int cur_sum = 0, old_sum = 0;
//    for (int i = 0; i < numsSize; i++) {
//        if (arr[nums[i]] == 1) { //这个数字在上边数组的对应位置已经置过1了，则重复
//            ret[0] = nums[i];//找到重复的数字
//        }
//        arr[nums[i]] = 1; //将标记数组的对应数据位置1
//        old_sum += i + 1; // 1~n的求和
//        cur_sum += nums[i]; //当前数组中的数据求和（多了一个重复的，少了一个丢失的）
//    }
//    ret[1] = old_sum - (cur_sum - ret[0]);//原始总和，减去去掉重复后的当前总和就是丢失的数字
//    free(arr);
//    return ret;
//}


//描述
//给定一个长度为 n 的非降序数组和一个非负数整数 k ，要求统计 k 在数组中出现的次数
//
//数据范围：0 \le n \le 1000, 0 \le k \le 1000≤n≤1000, 0≤k≤100，数组中每个元素的值满足 0 \le val \le 1000≤val≤100
//要求：空间复杂度 O(1)O(1)，时间复杂度 O(logn)O(logn)
//#include <stdio.h>
//
//int GetNumberOfK(int* data, int dataLen, int k) {
//    // write code here
//    int len = 0;
//    int left = 0;
//    int right = dataLen - 1;
//    if (right < 0)
//    {
//        return 0;
//    }
//    while (left < right)
//    {
//        int mid = (left + right) / 2;
//        if (data[mid] >= k)
//        {
//            right = mid;
//        }
//        else if (data[mid] < k)
//        {
//            left = mid + 1;
//        }
//    }
//    while (data[left] == k)
//    {
//        len++;
//        left++;
//    }
//    return len;
//}
//int main()
//{
//    int arr[6] = { 1,2,3,3,3,3 };
//    int k = 3;
//    int len = GetNumberOfK(arr, 6, 3);
//    printf("%d", len);
//    return 0;
//}

//int majorityElement(int* nums, int numsSize) {
//	int count = 1;
//	int tmp = nums[0];
//	for (int i = 1; i < numsSize; i++) {
//		if (tmp == nums[i]) {//与保存的字符相同则计数+1
//			count++;
//		}
//		else {//与保存的字符不同则计数-1
//			count--;
//			//计数为0表示有可能保存的字符不是最多的字符，换下一个
//			if (count == 0) tmp = nums[i + 1];
//		}
//	}
//	return tmp;
//}

int* productExceptSelf(int* nums, int numsSize, int* returnSize) {
	int* ret = (int*)malloc(numsSize * sizeof(int));
	*returnSize = numsSize;
	int left = 1, right = 1;
	//第一次循环，将当前位置左边的数字乘积填入返回数组中
	for (int i = 0; i < numsSize; i++) {
		ret[i] = left;// 1 nums[0] nums[0]*nums[1] num[0]*nums[1]*nums[2] ....
		left *= nums[i];
	}
	//第二次循环，对于返回数组的元素从后往前进行，每次乘以右边元素的乘积
	for (int i = numsSize - 1; i >= 0; i--) {
		ret[i] *= right; //最后一个成绩不需要乘以最后元素，乘以1就行
		right *= nums[i]; //right变化：1 nums[end] nums[end]*nums[end-1] .....
	}
	return ret;
}
